/*
 * @Author: wwssaabb
 * @Date: 2021-12-07 10:08:16
 * @LastEditTime: 2021-12-07 14:35:19
 * @FilePath: \handwritten-code\algorithm\合并两个有序链表.js
 */

/* 
将两个升序链表合并为一个新的 升序 链表并返回。 新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
输入： l1 = [1, 2, 4], l2 = [1, 3, 4]
输出：[1, 1, 2, 3, 4, 4]

示例 2：
输入： l1 = [], l2 = []
输出：[]

示例 3：
输入： l1 = [], l2 = [0]
输出：[0]

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/merge-two-sorted-lists
*/

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}
let list1 = new ListNode(1, new ListNode(2, new ListNode(4)))
let list2 = new ListNode(1, new ListNode(3, new ListNode(4)))

//双指针,时间复杂度O(n+m),空间复杂度O(n+m)
var mergeTwoLists = function (l1, l2) {
  let res = new ListNode()
  let l3 = res
  while (l1 && l2) {
    if (l1.val < l2.val) {
      l3.next = l1
      l1 = l1.next
    } else {
      l3.next = l2
      l2 = l2.next
    }
    l3 = l3.next
  }
  l3.next = (l1 ? l1 : l2)
  return res.next
};

console.log(mergeTwoLists(list1, list2)) //[ 1, 1, 2, 3, 4, 4 ]